Замена Heap на преалоцированный Vec + Lifetime переменные
TL;DR: Такой рефакторинг привел всех в состояние Х. С 7мкс до 200нс (буст в 35 раз). В вопросе скорости создания контекстов мы выебали Kx Systems, Erlang и Python. На этом можно поставить пока точку.
Мы поменяли в нашем интерпретаторе все Box Heap аллокации на преалоцированный ручной хип с вектором указателей + лайфтайм по всему коду. Т.е. даже Box остались исключительно как бинды. Получился Zero-Copy Interpreter работающий исключительно с указателями на ячейки байт-кода виртуальной машины, которые в сущности сериализированные элементы AST дерева. Опуская детали реализации приведу только типы деревьев:
Старое дерево с Heap указателями
Новое дерево только с абстрактными ссылками и переменными времени жизни
Environment в наивном прототипе представлен в виде HashMap, который как известно неподходит там где нужна скорость, зато понятно — у каждой кложи своя хеш-таблица контекст. Другое дело что для этого всего хватит и стека фреймов. Вообще говоря контексты функций — это и есть стек, а перенесен он в Heap для того, чтобы можно было писать не валящиеся бесконечные циклы, что называется tailcall или CPS интерпретаторами.
Написать прототип на расте оказалось очень просто. Бездумный ленивый CPS интерпретатор, который в хипе держит свой стек в виде HashMap изначально является не хуже чем LuaJIT в вопросе создания контекстов, а переписанный нормально в zero-copy версию с лайфтаймами с стек-фреймами в преалоцированном векторе обгоняет даже лидеров индустрии.
В рабочем режиме расставить амперсанты по коду заняло приблизительно 3 дня (чтобы получить 200нс версию), столько же времени ушло на создание изначального 7мкс прототипа. За скобками осталось влияние замены хештаблиц в качестве носителей контекстов на стековые фреймы в носителе-векторе, думаю заслуга этой части тоже немалая.
Это не первый интерпретатор с монотонно-растущими адресами, а значит существует функция ограничивающая расстояние до самого древнего индекса в ленте интерпретатора, на который хоть кто-то ссылается. Хочется сделать так чтобы расстояние до этого самого древнего индекса всегда было меньше N, чтобы закольцевать и замуровать его в ограниченном буфере-очереди-стриме. Сам интерпретатор является продюсером и консамером четырех стримов, т.е. его устройство полностью линеаризировано.